#include <stdio.h>
#include <stdlib.h>
//后缀表达式（逆波兰表达式）
//先声明一个顺序栈
#define MAXSIZE 100
typedef int ElemType;
typedef struct 
{
    ElemType *data;
    int top;
}Stack;
//初始化
Stack *initstack()
{
    Stack *s=(Stack *)malloc(sizeof(Stack));
    s->data=(ElemType *)malloc(sizeof(ElemType)*MAXSIZE);
    s->top=-1;
    return s;
}
//枚举常量：为了辨认遍历时遇到的字符是什么类型，该进行怎样的操作
typedef enum
{
    Left_pare,Right_pare,add,sub,mul,Div,mod,eos,num
//    '('         ')'    '+' '-' '*' '/' '%' '\0'  操作数
//     0           1      2   3   4   5   6    7     8
}contentType;
//但其实后缀表达式中没有括号
//全局变量：要进行计算的后缀表达式
char expr[]="82/2+56*-";
//入栈
int push(Stack *s,ElemType n)
{
    if(s->top>=MAXSIZE-1)
    {
        printf("栈满了\n");
        return 0;
    }
    s->top++;
    s->data[s->top]=n;
    return 1;
}
//出栈
int pop(Stack *s,ElemType *op)
{
    if(s->top==-1)
    {
        printf("空栈\n");
        return 0;
    }
    *op=s->data[s->top];
    s->top--;
    return 1;
}
//对字符类型的辨认
contentType getToken(char *symbol,int *i)
{
    *symbol=expr[*i];
    (*i)++;  //遍历数组
    switch(*symbol)
    {
        case '(':
        return Left_pare;
        case ')':
        return Right_pare;
        case '+':
        return add;
        case '-':
        return sub;
        case '*':
        return mul;
        case '/':
        return Div;
        case '%':
        return mod;
        case '\0':
        return eos;
        default:
        return num;
    }
}
//计算
void RPV(Stack *s)
{
    char symbol;  //将遍历到的每一个字符存进来
    //就是为了把每个字符单拎出来看
    ElemType op1,op2;  //两个操作数，为了运算
    int i=0;//数组下标：为了遍历字符串
    contentType token;
    token =getToken(&symbol,&i); //将遍历到的字符的类型存进token
    //这里&symbol还有&i都是为了在函数里改变他们本身的值
    while(token!=eos)
    {
        if(token==num)
        {
            push(s,symbol-'0'); //将字符变成数字
        }
        else
        {
            pop(s,&op2);
            pop(s,&op1);
            switch(token)
            {
                case add:
                push(s,op1+op2);
                break;
                case sub:
                push(s,op1-op2);
                break;
                case mul:
                push(s,op1*op2);
                break;
                case Div:
                push(s,op1/op2);
                break;
                case mod:
                push(s,op1%op2);
                break;
                default:
                break;
            }
        }
        token =getToken(&symbol,&i); //继续遍历
    }
    ElemType result;
    pop(s,&result);
    printf("%d\n",result);
}
int main()
{
    Stack *s=initstack();
    //进行后缀表达式计算
    RPV(s);
    return 0;
}
//输出：-24